class Solution:
     # [72. 编辑距离](https://leetcode.cn/problems/edit-distance/description/?envType=problem-list-v2&envId=dynamic-programming)
     def minDistance(self, word1: str, word2: str) -> int:
            m, n = len(word1), len(word2)
            # dp[i][j] 表示 word1[0..i]转换到word2[0..j]的最少操作数
            dp = [[0] * (n + 1) for _ in range(m+1)]
            # 初始化dp数组
            for i in range(m+1):
                dp[i][0] = i
            for j in range(n+1):
                dp[0][j] = j
            # 动态规划
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if word1[i-1] == word2[j-1]:
                        dp[i][j] = dp[i-1][j-1]
                    else:
                        dp[i][j] = min(
                            dp[i][j-1] + 1, # 插入
                            dp[i-1][j] + 1, # 删除
                            dp[i-1][j-1] + 1, # 替换
                        )

            return dp[m][n]

    # [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/description/?envType=problem-list-v2&envId=dynamic-programming)
    def numTrees(self, n: int) -> int:
        #  dp[i] 表示用 i 个节点能构成的不同二叉搜索树的种数
        dp = [0] * (n + 1)

        dp[0] = dp[1] = 1  # 空树和单节点树各有一种

        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]  # 选择j为根节点，左子树有j-1个节点，右子树有i-j个节点

        return dp[n]

    # [95. 不同的二叉搜索树 II](https://leetcode.cn/problem-list/dynamic-programming/)
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return [None]

        return self._generateTrees(1, n)

    def _generateTrees(self, start, end):
        if start > end:
            return [None]

        result = []
        # 递归创建左右子树
        for i in range(start, end + 1):
            left_tree = self._generateTrees(start, i - 1)
            right_tree = self._generateTrees(i + 1, end)

            # 构建以i为根节点的树
            for left in left_tree:
                for right in right_tree:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    result.append(root)

        return result

        # [118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/description/?envType=problem-list-v2&envId=dynamic-programming)


def generate(self, numRows: int) -> List[List[int]]:
    triangle = []

    for rowIndex in range(numRows):
        new_row = [1] * (rowIndex + 1)  # 默认全是1

        for j in range(1, rowIndex):  # 计算第rowIndex行的元素
            new_row[j] = triangle[rowIndex - 1][j - 1] + triangle[rowIndex - 1][j]

        triangle.append(new_row)

    return triangle

    # [119. 杨辉三角 II](https://leetcode.cn/problems/pascals-triangle-ii/?envType=problem-list-v2&envId=dynamic-programming)
    def getRow(self, rowIndex: int) -> List[int]:
        # 初始行是 [1]
        row = [1]

        # 从第二行开始，逐步计算每一行
        for i in range(1, rowIndex + 1):
            # 创建一个新的行，长度是 i + 1
            new_row = [1] * (i + 1)

            # 从第二个元素开始，计算每个元素的值
            for j in range(1, i):
                new_row[j] = row[j - 1] + row[j]

            # 更新 row 为新的行
            row = new_row

        return row

    # [198. 打家劫舍](https://leetcode.cn/problems/house-robber/submissions/622333638/?envType=problem-list-v2&envId=dynamic-programming)

    def rob1(self, nums: List[int]) -> int:
        n = len(nums)
        # 特殊情况判断
        if n == 0:
            return 0
        elif n == 1:
            return nums[0]

        dp_steal = [0] * n  # dp_steal[i]: 偷取第i家的最大金额
        dp_skip = [0] * n  # dp_skip[i]: 不偷取第i家的最大金额

        dp_steal[0] = nums[0]
        dp_skip[0] = 0

        for i in range(1, n):
            dp_steal[i] = dp_skip[i - 1] + nums[i]
            dp_skip[i] = max(dp_skip[i - 1], dp_steal[i - 1])

        # 返回最后一间房屋的最大收益
        return max(dp_skip[n - 1], dp_steal[n - 1])


    def rob2(self, nums: List[int]) -> int:
        n = len(nums)
        # 特殊情况判断
        if n == 0:
            return 0
        elif n == 1:
            return nums[0]

        # 空间优化，使用变量代替dp数组
        prev_steal = nums[0]
        prev_skip = 0

        for i in range(1, n):
            cur_steal = prev_skip + nums[i]
            cur_skip = max(prev_steal, prev_skip)

            prev_steal = cur_steal
            prev_skip = cur_skip

        # 返回最后一间房屋的最大收益
        return max(prev_skip, prev_steal)

    # [337. 打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/submissions/622676476/?envType=problem-list-v2&envId=dynamic-programming)
    def rob(self, root: Optional[TreeNode]) -> int:
        # 辅助函数: 返回当前节点的最大金额
        def dfs(node):
            if not node:
                return [0, 0]

            # 递归左右子树的值
            left = dfs(node.left)
            right = dfs(node.right)

            not_rob = max(left[0], left[1]) + max(right[0], right[1])  # 不偷当前节点，则左右子树可以偷
            rob = node.val + left[0] + right[0]

            return [not_rob, rob]

        result = dfs(root)
        return max(result[0], result[1])

    # [343. 整数拆分](https://leetcode.cn/problems/integer-break/description/?envType=problem-list-v2&envId=dynamic-programming)
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        elif n == 3:
            return 2

        # 尽可能地拆分多个3，以4为最低限度值。
        product = 1
        while n > 4:
            product *= 3
            n -= 3

        product *= n  # 乘剩下的值

        return product

    # [392. 判断子序列](https://leetcode.cn/problems/is-subsequence/description/?envType=problem-list-v2&envId=dynamic-programming)
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        s_len, t_len = len(s), len(t)

        # 遍历 t，直到 t 遍历完或者 s 遍历完
        while i < s_len and j < t_len:
            if s[i] == t[j]:  # 如果匹配，则 i 增加，继续找下一个字符
                i += 1
            j += 1

        # 如果 i 达到 s 的长度，说明 s 是 t 的子序列
        return i == s_len

    # [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/description/?envType=problem-list-v2&envId=dynamic-programming)
    def partition(self, s: str) -> List[List[str]]:
        result = []
        n = len(s)

        # 辅助函数: 判断是否是回文串
        def is_palindrome(str):
            return str == str[::-1]

        def dfs(start, path):
            if start == n:  # 如果起始位置到达字符串末尾，说明找到了一种有效的分割
                result.append(path[:])  # 将当前分割方案加入结果
                return

                # 从当前位置开始遍历
            for end in range(start + 1, n + 1):
                substr = s[start:end]
                if is_palindrome(substr):
                    path.append(substr)  # 如果是回文串，加入当前分割
                    dfs(end, path)  # 递归处理剩余的部分
                    path.pop()  # 回溯，移除当前的分割

        # 从字符串的开始位置开始回溯
        dfs(0, [])
        return result

    # [120. 三角形最小路径和](https://leetcode.cn/problems/triangle/description/?envType=problem-list-v2&envId=dynamic-programming)
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # 从底部到顶部动态规划
        n = len(triangle)

        # dp 数组从底层开始处理，直接用 triangle 最后一行初始化
        dp = triangle[-1]

        # 从倒数第二行开始往上处理
        for row in range(n - 2, -1, -1):  # 从倒数第二行开始，直到第一行
            for i in range(len(triangle[row])):
                # 更新 dp 数组中的值，代表从当前位置向下的最小路径和
                dp[i] = triangle[row][i] + min(dp[i], dp[i + 1])

        # 最终 dp[0] 就是从顶端到达底端的最小路径和
        return dp[0]

    # [509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/?envType=problem-list-v2&envId=dynamic-programming)
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1

        return self.fib(n - 1) + self.fib(n - 2)

    # [1. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/description/)
    def longestCommonSubsequence(text1, text2):
        m, n = len(text1), len(text2)

        # 定义 dp 数组
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]


    # [最长公共子序列(二)](https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&tqId=991075&sourceUrl=/exam/oj?questionJobId=10&subTabName=online_coding_page)
    def LCS(s1, s2):
        m, n = len(s1), len(s2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # S1: 获取最长公共子序列长度
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        # S2: 根据 dp 反向构建出 lcs
        i, j = m, n
        lcs = ""
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                lcs = s1[i - 1] + lcs
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return lcs if lcs else "-1"